package com.zou.practice.sort;

import com.alibaba.fastjson.JSON;

/**
 * @author zouyaowen
 * @date 2020-09-13
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {13, 3, 2, 9, 8, 11};
        System.out.println(JSON.toJSONString(arr));
        // shellSort(arr);
        shellSortSecond(arr);
        System.out.println(JSON.toJSONString(arr));
    }


    /**
     * 排序实现
     *
     * @param arr 排序数据
     */
    private static void shellSortSecond(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int gap = arr.length / 2;
        while (gap >= 1) {
            //从分组索引处开始遍历
            for (int i = gap; i < arr.length; i++) {
                //获取前一个数据索引
                int pre = i - gap;
                //获取当前索引位置数据
                int current = arr[i];
                //循环条件:前一个数据索引最小为0,前一个数据大于当前数据
                for (; pre >= 0 && arr[pre] > current; pre -= gap) {
                    //将前一个数据后移
                    arr[pre + gap] = arr[pre];
                }
                //如果循环条件不满足，将数据存储至当前索引
                arr[pre + gap] = current;
            }
            gap /= 2;
        }
    }

    /**
     * @param arr 排序数据
     */
    private static void shellSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int n = arr.length;
        // 对每组间隔为 h的分组进行排序，刚开始 h = n / 2;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            //对各个局部分组进行插入排序
            for (int i = gap; i < n; i++) {
                // 将arr[i] 插入到所在分组的正确位置上
                insertPosition(arr, gap, i);
            }
        }
    }

    /**
     * 数据插入正确的位置
     *
     * @param arr 数组
     * @param gap 增量分组间隔
     * @param i   元素位置
     */
    private static void insertPosition(int[] arr, int gap, int i) {
        int inserted = arr[i];
        int k;
        for (k = i - gap; k >= 0 && inserted < arr[k]; k -= gap) {
            arr[k + gap] = arr[k];
        }
        arr[k + gap] = inserted;
    }
}
